In this paper we consider the wavelet synopsis construction problem withoutthe restriction that we only choose a subset of coefficients of the originaldata. We provide the first near optimal algorithm. We arrive at the abovealgorithm by considering space efficient algorithms for the restricted versionof the problem. In this context we improve previous algorithms by almost alinear factor and reduce the required space to almost linear. Our techniquesalso extend to histogram construction, and improve the space-running timetradeoffs for V-Opt and range query histograms. We believe the idea applies toa broad range of dynamic programs and demonstrate it by showing improvements ina knapsack-like setting seen in construction of Extended Wavelets.
展开▼
